/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package cz.dusa.switco;

import cz.dusa.switco.ScheduleReader.PrecedenceHolder;
import cz.dusa.switco.ScheduleReader.ScheduleModel;
import cz.dusa.switco.ScheduleReader.TaskHolder;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Schedule class implements methods allowing creation of the optimal schedule. First of all 
 * insert tasks into the schedule using {@link #addTask(cz.dusa.switco.Task)}. Then insert all 
 * precedences using {@link #addPrecedence(cz.dusa.switco.Task, cz.dusa.switco.Task, java.lang.Double, java.lang.Double)}.
 * The schedule is immediately optimized after adding task or precedence.
 * @author vdusa
 */
public class Schedule {

    private final boolean VERBOSE = false;

    private interface ShiftTarget{
        public double getShift();
    }

    private class ShiftTargetRepairPrecedence implements ShiftTarget {
        private Precedence precedence;

        private ShiftTargetRepairPrecedence(){}

        public ShiftTargetRepairPrecedence(Precedence precedence){
            this.precedence = precedence;
        }

        public double getShift() {
            return precedence.getPredecessor().getStart()+precedence.getValue() - precedence.getSuccessor().getStart();
        }
    }

    private class ShiftTargetOnTimeTree implements ShiftTarget{
        Task pivot;

        private ShiftTargetOnTimeTree(){}

        public ShiftTargetOnTimeTree(Task pivot){
            this.pivot = pivot;
        }

        public double getShift() {
            EqualityTree tree = pivot.getEqualityTree();
            Double[] optimalTimeWindow = tree.getTasksHolder().getOptimalStartTimeWindow();

            if (optimalTimeWindow[0]<=tree.getStart() && tree.getStart()<=optimalTimeWindow[1]){
                return 0;
            } else{
                if(tree.getStart() < optimalTimeWindow[0]){
                    //tree is strictly early
                    return optimalTimeWindow[0] - tree.getStart();
                } else {
                    //tree is strictly late
                    return optimalTimeWindow[1] - tree.getStart();
                }
            }
        }
    }
    
    private interface SolutionExistencyWatchdog{
        public boolean solutionExists();
    }
    
    private class SolutionExistencySleepingWatchdog implements SolutionExistencyWatchdog{        
        public boolean solutionExists() {
            return true;
        }
    }

    private class SolutionExistencyWatchdogForNewPrecedence  implements SolutionExistencyWatchdog {
        private Precedence precedence;
        
        private SolutionExistencyWatchdogForNewPrecedence(){}
        
        /**
         * @param precedence Precedence, that is currently added to the schedule. 
         * Predecessor and successor of this precedence weren't informed about it yet.
         */
        public SolutionExistencyWatchdogForNewPrecedence(Precedence precedence){
            this.precedence = precedence;
        }

        /**
         * As soon as both tasks are in same tree and there is a path from successor
         * to the predecessor in the active equality tree (it means only active edges), 
         * then the precedence currently being added would create circle, thus 
         * no solution exists
         * @return false if above described condition is satisfied. Otherwise true.
         */
        public boolean solutionExists(){
            Task predecessor = precedence.getPredecessor();
            Task successor = precedence.getSuccessor();
            if(predecessor.getEqualityTree().equals(successor.getEqualityTree())){
                //successor and predecessor are in same tree - we have to check it
                EqualityTree tree = precedence.getPredecessor().getEqualityTree();
                if(tree.existsDirectedPath(successor, predecessor) && precedence.isViolated()){
                    return false;
                }
            }

            return true;
        }
    }

    public Schedule() {
    }

    ;

    /**
     * Adds a new task into the schedule and optimizes the schedule imediately.
     *
     * @param task is the task being added into the schedule.
     */
    public void addTask(Task task) {
        assert task.getPredecessors().isEmpty() && task.getSuccessors().isEmpty() : "Tasks added to the schedule can not contain any precedence. Please add precedences later.";

        List<Task> tasks = new ArrayList<Task>();
        tasks.add(task);
        EqualityTree tree = new EqualityTree(tasks, null);
        task.setEqualityTree(tree);
        tree.setStart(0);
        Forest.getInstance().plantTree(tree);

        makeTreeOnTime(task);
    }

    /**
     * Adds a new precedence into the schedule and optimizes the schedule imediately.
     *
     * @param predecessor is a predecessor Task
     * @param successor is a successor Task
     * @param maximumPossibleDistance is a maximal possible distance between predecessor.getFinish() and successor.getStart().
     * Use Double.NaN no such distance is defined .
     * @param minimumDistance  is a minimal possible distance between predecessor.getFinish() and successor.getStart(). use 0
     * if no such distance is defined.
     */
    public void addPrecedence(Task predecessor, Task successor, Double maximumPossibleDistance, Double minimumDistance) {
        double regularValue = minimumDistance + predecessor.getProcessingTime();
        double ropeValue = -predecessor.getProcessingTime() - maximumPossibleDistance;

        Precedence p = new Precedence(predecessor, successor);
        p.setType(PrecedenceType.REGULAR);
        p.setValue(regularValue);
        optimize(p);

        if (!maximumPossibleDistance.equals(Double.NaN)) {
            /*see Problem definition and notation section in the article
             * if there is a maximum distance defined, then we have to create a second precedence (predecessor, successor)
             */

            Precedence reversePrecedence = new Precedence(successor, predecessor);
            reversePrecedence.setType(PrecedenceType.ROPE);
            reversePrecedence.setValue(ropeValue);
            optimize(reversePrecedence);
        }
    }

    private void shift(Task pivot, ShiftTarget target, SolutionExistencyWatchdog watchdog) {        
        MovingDirection direction;
        double difference = target.getShift();

        //direction remains unchanged during whole while loop
        direction = difference>0?MovingDirection.FORWARD:MovingDirection.BACKWARDS;
        
        while(GlobalSettings.getInstance().roundToPrecisionLimit(difference) != 0) {
            EqualityTree tree = pivot.getEqualityTree();
            
            Event event = tree.getNearestEvent(direction, pivot);
            
            if (event != null) {
                double eventTreeStart = event.getTime();
                double eventDifference = eventTreeStart - tree.getStart();
                if(Math.abs(eventDifference) < Math.abs(difference)){ //either both eventDifference and difference are negative or both are positive.
                    tree.setStart(eventTreeStart); //set the new start
                    switch (event.getType()) {
                        case MERGE:
                            //System.out.println("MERGE:");
                            tree.merge(event.getPrecedence());
                            if(!watchdog.solutionExists()){
                                throw new NoSolutionException("There is no solution");
                            }
                            
                            break;
                        case SPLIT:
                            //System.out.println("SPLIT:");
                            tree.split(event.getPrecedence());
                            break;
                        default:
                            throw new RuntimeException("Unknown EventType " + event.getType().toString());
                    }
                } else {
                    tree.setStart(tree.getStart() + difference);
                }

            } else {
                tree.setStart(tree.getStart() + difference); //set the new start
            }

            difference = target.getShift();
        }
    }

    private void makeTreeOnTime(Task pivot){
        shift(pivot, new ShiftTargetOnTimeTree(pivot), new SolutionExistencySleepingWatchdog());
    }

    /**
     * Optimizes the EqualityTree in which the task is contained
     * @param task - the task (e.g. its equality tree) to be optimized
     * @param precedence - currently added precedence (this parameter can be also null in case of optimizing
     * alone task). This precedence see its predecessor and successor
     * but these tasks don't see the precedence. As soon as the forward shift is finished, predecessor
     * and successor are informed about the new precedence and then the backward shift takes also this 
     * precedence into account. 
     */
    private void optimize(Precedence precedence) throws NoSolutionException, RuntimeException {
        /* precondition of this funciton is, that only the given tree is not on time, but all other
         * trees in the schedule are on time and the only precedence that can be violated is heading into
         * the given task.
         */

        if(precedence.isViolated()){
            Task predecessor = precedence.getPredecessor();
            Task successor = precedence.getSuccessor();
            shift(successor, new ShiftTargetRepairPrecedence(precedence), new SolutionExistencyWatchdogForNewPrecedence(precedence));
            precedence.informTasks();
            makeTreeOnTime(successor);
            successor.getEqualityTree().splitAtInactivePrecedences();
        } else{
            precedence.informTasks();
        }
    }

    /**
     * @param a
     * @param b
     * @return minimum of a,b
     */
    private static double min(double a, double b) {
        return a <= b ? a : b;
    }

    /**
     * main method is here only for purpose of testing and profiling of the source code.
     * @param args 
     */
    public static void main(String[] args) {
        ScheduleModel model = ScheduleReader.getInstance().read("test_schedule.xml");
        Schedule schedule = new Schedule();

        for (TaskHolder taskHolder : model.tasks.values()) {
            Task task = new Task(taskHolder.id, ConvexCostFunctionFactory.getInstance().getConvexCostFunction(taskHolder.costFunction), taskHolder.processingTime);
            schedule.addTask(task);
        }

        for (PrecedenceHolder precedenceHolder : model.precedences) {
            Task predecessor = Forest.getInstance().getTask(precedenceHolder.predecessor);
            Task successor = Forest.getInstance().getTask(precedenceHolder.successor);
            schedule.addPrecedence(predecessor, successor, precedenceHolder.maxDistance, precedenceHolder.minDistance);

            if (!Forest.getInstance().isOptimal()) {
                System.err.println("Schedule is not optimal after adding new precedence. Something is wrong!");
            }
        }

        if (Forest.getInstance().isOptimal()) {
            System.out.println("We have an optimal schedule! :)");
        }
    }
}
